/*
 * RegionLabeling.cpp
 *
 *  Created on: 04.11.2013
 *      Author: Patrick
 */

#include <vector>

#include <engine/datatypes/DisjointSet.hpp>

#include <engine/algorithms/RegionLabeling.h>

namespace Engine {

bool RegionLabeling::getRegions(
		std::vector<std::vector<float> >* values,
		float threshold,
		std::vector<std::vector<int> > &regions,
		std::vector<int> &regionLabels) {

	unsigned int width = values->size();
	unsigned int height = values[0].size();

	if(width != regions.size() || height != regions[0].size()) {
		return false;
	}

	DisjointSet labels = DisjointSet();
	int regionsCounter = 1;

	//**********
	//First Pass
	//**********

	// 0, 0
	if(values->at(0)[0] >= threshold) {
		labels.insert(regionsCounter);
		regions[0][0] = regionsCounter;
		regionsCounter++;
	}

	// i, 0
	for(unsigned int i = 1; i < width; i++) {
		float value = values->at(i)[0];
		if(value >= threshold && values->at(i-1)[0] >= threshold) {
			regions[i][0] = regions[i-1][0];
		} else if(value >= threshold) {
			labels.insert(regionsCounter);
			regions[i][0] = regionsCounter;
			regionsCounter++;
		}
	}

	// 0, j
	for(unsigned int j = 1; j < height; j++) {
		float value = values->at(0)[j];
		if(value >= threshold && values->at(0)[j-1] >= threshold) {
			regions[0][j] = regions[0][j-1];
		} else if(value >= threshold) {
			labels.insert(regionsCounter);
			regions[0][j] = regionsCounter;
			regionsCounter++;
		}
	}

	// i, j
	for(unsigned int i = 1; i < width; i++) {
		for(unsigned int j = 1; j < height; j++) {
			float value = values->at(i)[j];
			float left = values->at(i-1)[j];
			float up = values->at(i)[j-1];
			if(value >= threshold && left >= threshold && up >= threshold) {
				if(regions[i-1][j] < regions[i][j-1]) {
					regions[i][j] = regions[i-1][j];
					labels.Union(regions[i-1][j], regions[i][j-1]);
				} else if(regions[i-1][j] > regions[i][j-1]) {
					regions[i][j] = regions[i][j-1];
					labels.Union(regions[i-1][j], regions[i][j-1]);
				} else {
					regions[i][j] = regions[i-1][j];
				}
			} else if(value >= threshold && left >= threshold) {
				regions[i][j] = regions[i-1][j];
			} else if(value >= threshold && up >= threshold) {
				regions[i][j] = regions[i][j-1];
			} else if(value >= threshold) {
				labels.insert(regionsCounter);
				regions[i][j] = regionsCounter;
				regionsCounter++;
			}
		}
	}

	//***********
	//Second Pass
	//***********

	for(unsigned int i = 0; i < width; i++) {
		for(unsigned int j = 0; j < height; j++) {
			if(regions[i][j] != 0) {
				regions[i][j] = labels.findRootValue(regions[i][j]);
			}
		}
	}

	regionLabels = labels.getRoots();

	return true;
}

} /* namespace Engine */
